#include <iostream>
using namespace std;
typedef struct node
{
    int data;
    struct node *next;
}Node,*LNode;

void insertnode(LNode &H,int x)//元素非递减插入链表
{
    Node *p, *q, *r;//r前驱，p工作指针,q创结点
    r = H;
    p = H->next;
    while(p!=NULL&&p->data<x)
    {
        r = p;
        p = p->next;
    }
    q = new Node;
    q->data=x;
    q->next=p;
    r->next=q;
}

void cinnode(LNode &H)//输入元素
{
    H = new Node;
    if(H==NULL)
    {
        cout << "无内存空间可分配" << endl;
        return;
    }
    H->next = NULL;
    int x;
    cin >> x;
    while(x!=0)
    {
        insertnode(H, x);//将元素插入链表
        cin >> x;
    }
}

void outputnode(LNode &H)//输出链表
{
    Node *p;
    p=H->next;
    while(p!=NULL)
    {
        cout << p->data << ' ';
        //printf("%d  ",p->data);
        p=p->next;
    }
}

void link(LNode &HA,LNode &HB)//递减可重复连接链表A,B，头插连接（原链表非递减）
{
    Node *pa, *paa, *pb, *pbb;
    pa = HA->next;//记录A链表首元结点
    pb = HB->next;//记录B链表首元结点
    HA->next = NULL;
    HB->next = NULL;
    while(pa!=NULL&&pb!=NULL)
    {
        if(pa->data<pb->data)
        {
            paa = pa->next;
            pa->next = HA->next;
            HA->next = pa;
            pa = paa;
        }
        else
        {
            pbb = pb->next;
            pb->next = HA->next;
            HA->next = pb;
            pb = pbb;
        }
    }
    while(pa!=NULL)
    {
        paa = pa->next;
        pa->next = HA->next;
        HA->next = pa;
        pa = paa;
    }
    while(pb!=NULL)
    {
        pbb = pb->next;
        pb->next = HA->next;
        HA->next = pb;
        pb = pbb;
    }
}

int main()
{
    LNode HA,HB;
    cinnode(HA);
    cinnode(HB);
    link(HA, HB);
    outputnode(HA);
    return 0;
}
